/*
*  heapADT.c
*  =========
*  Implementacion de la parva definida en heapADT.h
*  
*/
#include <stdio.h>
#include <stdlib.h>
#include "heapADT.h"

#define INICIAL 20
#define INCREMENT 10

#define ERROR(cartel, rpta)  {\
                                fprintf(stderr, cartel);\
                                return rpta;\
                              } 

struct heapCDT{
    elementType *datos;
    int size;
    int posic;
    int(*compFn)(elementType elem1, elementType elem2);
    void(*printFn)(elementType elem);
};

heapADT 
NewHeap(int(*compFn)(elementType elem1, elementType elem2), void(*printFn)(elementType elem))
{
    heapADT parva;
    
    if( (parva=malloc(sizeof(struct heapCDT))) == NULL )
        ERROR("NewHeap: No hay memoria para la parva\n", NULL);
        
    parva->size = INICIAL;   
    if( (parva->datos=malloc(sizeof(elementType)*parva->size)) == NULL )
    {
        free(parva);
        ERROR("NewHeap: No hay memoria el arreglo interno\n", NULL); 
    }
    parva->posic = -1;
    parva->compFn = compFn;
    parva->printFn = printFn;
    return parva;  
}

void 
FreeHeap(heapADT parva)
{
    if( parva != NULL )
    {
        free(parva->datos);
        free(parva);
    }
    return;
}


int 
HeapIsEmpty(heapADT parva)
{
    if(parva == NULL)
        ERROR("HeapIsEmpty: parva no incializada\n", 1); 
      
    return parva->posic == -1;    
}

void 
ListElements(heapADT parva)
{
    int i;
    
    if(parva == NULL)
        ERROR("ListElements: parva no incializada\n", ); 
    if( !HeapIsEmpty(parva) )    
    {
        for(i=0; i<=parva->posic; i++)
            //fprintf(stdout,"\t%d", *parva->datos[i]);
        	parva->printFn( parva->datos[i] );
        fprintf(stdout,"\n");    
    }        
    else    
        fprintf(stdout,"ListElements:La parva esta vacia\n");       
    return;
}

static int
padre(int h)
{
    return (h-1)/2;
}

static int
hijoIzq(int p)
{
    return 2*p+1;
}

static int
hijoDer(int p)
{
    return 2*p+2;
}

static void
swap(elementType *datos, int i, int j)
{
    elementType aux;
    
    aux = datos[i];
    datos[i] = datos[j];
    datos[j] = aux;
    return;
}



static void
ordenarI( heapADT parva, int h )
{
    int p;
    
    if( h == 0 )
        return;
    else
    {    
        p = padre(h);
        if( parva->compFn( parva->datos[h], parva->datos[p] ) > 0 )
        {
            swap(parva->datos, h, p);
            ordenarI(parva, p);        
        }
        return;
    }   
}

void 
InsertElement(heapADT parva, elementType elem)
{
    if(parva == NULL)
        ERROR("InsertElement: parva no incializada\n", ); 
    
    parva->datos[++parva->posic] = elem;
    ordenarI(parva, parva->posic);        
    return;
}

static int
PosicHijoMayor(heapADT parva, int p)
{
    int hi, hd;
    
    hi = hijoIzq(p);
    hd = hijoDer(p);
    
    if( hi<= parva->posic && hd<= parva->posic)
    {
        if( parva->compFn(parva->datos[hi],parva->datos[hd]) >= 0 )
            return hi;
        else    
            return hd;
    }        
    else if(hi > parva->posic && hd > parva->posic)
            return parva->posic+1;        
         else
            return parva->posic; 
            /* la unica posibilidad es que uno de los hijos cae 
            *  justo en parva->posic, y el otro debe caer en el 
            *  lugar siguiente.
            *  Retorno la parva->posic para que se realize la 
            *  comparacion ya que puede ser necesario un swap.                                                                                                                                                                                                     
            */   
} 

static void
ordenarG(heapADT parva, int p)
{
    int h;
        
    if( p >= parva->posic)
        return;
    else
    {
        h = PosicHijoMayor(parva, p);
        if( h <= parva->posic && parva->compFn(parva->datos[p],parva->datos[h]) < 0 )
        {
            swap(parva->datos, p, h);
            ordenarG(parva, h);
        }
        return;
    }
}

int 
GetElement(heapADT parva, elementType *elem)
{
    elementType aux;
    
    if(parva == NULL)
        ERROR("GetElement: parva no incializada\n", 1); 
    if( HeapIsEmpty(parva) )    
        ERROR("GetElement: parva vacia\n", 2); 
    
    *elem = parva->datos[0];   
    aux = parva->datos[parva->posic];
    parva->posic--;
    if( !HeapIsEmpty(parva) )
    {    
        parva->datos[0] = aux;
        ordenarG(parva, 0);
    }    
    return 0;    
}
